package Tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 437.路径总和|||
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 */
public class pathSum {
    /**
     * hot100一刷
     */
    int res = 0;

    public int pathSum(TreeNode root, long targetSum) {
        traverse(root, targetSum);
        return res;
    }

    public void traverse(TreeNode root, long targetSum) {
        if (root == null) return;
        backtracking(root, targetSum);
        traverse(root.left, targetSum);
        traverse(root.right, targetSum);
    }

    public void backtracking(TreeNode root, long targetSum) {
        if (root == null)
            return;
        if (root.val == targetSum) {
            res++;
        }
        backtracking(root.left, targetSum - root.val);
        backtracking(root.right, targetSum - root.val);
    }


    /**
     * hot100二刷
     */
    class Solution {
        int res = 0;
        Map<Long, Integer> map = new HashMap<>();
        // map用来存放当前递归分支上已经出现过的前缀和。注意节点的取值范围要使用Long

        public int pathSum(TreeNode root, int targetSum) {
            map.put(0L, 1);  // 注意先在map中放入0，不然当前缀和正好等于 targerSum 时没法被计入 res。注意这里要做 int -> Long 的类型转换
            traversal(root, targetSum, 0L); // 这里也要做 int -> Long 的类型转换
            return res;
        }

        public void traversal(TreeNode node, int targetSum, Long sum) {  // 由于节点值的范围是Long，所以节点的和的类型也应该是Long
            // 参数sum表示前缀和（从根节点到当前节点的所有节点之和）
            if (node == null) return;

            sum += node.val;
            if (map.containsKey(sum - targetSum)) {
                res += map.get(sum - targetSum);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);

            traversal(node.left, targetSum, sum);   // sum不能是全局变量，而必须是递归函数的参数。否则在这里向左递归后，sum的值的变化会影响到接下来向右递归时sum的大小
            traversal(node.right, targetSum, sum);

            // 回溯。因为sum是递归函数参数，每个递归分支的sum之间互相独立，所以不用再手动回溯sum的值，只需要手动回溯map就够了
            map.put(sum, map.get(sum) - 1);
        }
    }

}
